Skip to main content

02. 布尔代数与逻辑函数化简

2.1 布尔代数基础 (Boolean Algebra Fundamentals)​

布尔代数是分析和简化数字逻辑电路的数学工具。它由一组元素、一组运算符和若干公理/定理构成。

  • 元素 (Elements): 二值变量，取值为 00 或 11。
  • 运算符 (Operators):
    • 与 (AND): 逻辑乘，用 ⋅\cdot 表示（常省略）。
    • 或 (OR): 逻辑加，用 ++ 表示。
    • 非 (NOT): 逻辑反，用 ′' 或 A‾\overline{A} 表示。
  • 运算优先级 (Operator Precedence): 括号 > 非 (NOT) > 与 (AND) > 或 (OR)

2.1.1 公理与定理 (Axioms and Theorems)​

公理和定理是进行逻辑表达式化简的基础。一个重要的性质是对偶性 (Duality)：将表达式中的 ⋅\cdot 与 ++ 互换，00 与 11 互换，等式依然成立。

单变量定理

定理表达式对偶形式名称
1x+0=xx + 0 = xx⋅1=xx \cdot 1 = x恒等律 (Identity)
2x+1=1x + 1 = 1x⋅0=0x \cdot 0 = 0零一律 (Null Element)
3x+x=xx + x = xx⋅x=xx \cdot x = x等幂律 (Idempotency)
4(x′)′=x(x')' = x反演律 (Involution)
5x+x′=1x + x' = 1x⋅x′=0x \cdot x' = 0互补律 (Complements)

多变量定理

定理表达式对偶形式名称
6x+y=y+xx + y = y + xxy=yxxy = yx交换律 (Commutativity)
7(x+y)+z=x+(y+z)(x + y) + z = x + (y + z)(xy)z=x(yz)(xy)z = x(yz)结合律 (Associativity)
8x(y+z)=xy+xzx(y + z) = xy + xzx+yz=(x+y)(x+z)x + yz = (x + y)(x + z)分配律 (Distributivity)
9x+xy=xx + xy = xx(x+y)=xx(x + y) = x吸收律 (Absorption)
10xy+xy′=xxy + xy' = x(x+y)(x+y′)=x(x + y)(x + y') = x合并律 (Combining)
11xy′+y=x+yxy' + y = x + y(x+y′)y=xy(x+y')y = xy化简律 (Simplification)
12xy+x′z+yz=xy+x′zxy + x'z + yz = xy + x'z(x+y)(x′+z)(y+z)=(x+y)(x′+z)(x+y)(x'+z)(y+z) = (x+y)(x'+z)共识律 (Consensus)
13(x+y)′=x′y′(x + y)' = x'y'(xy)′=x′+y′(xy)' = x' + y'德摩根定律 (DeMorgan's Law)

重点与难点解释

  • 分配律的对偶形式: x+yz=(x+y)(x+z)x + yz = (x + y)(x + z) 是布尔代数独有的，区别于普通代数，非常重要且常用。它常用于将“与或”式转换为“或与”式。
  • 德摩根定律 (DeMorgan's Law): 这是最重要的定理之一，用于求函数的反函数以及在不同逻辑门（如与非门、或非门）之间进行转换。
    • 口诀: “长线变短线，符号（⋅\cdot 和 ++）互换”。
    • 用例: 化简 (A′B+C)′(A'B + C)'
      1. 将整个表达式看作 (X+Y)′(X+Y)'，其中 X=A′B,Y=CX=A'B, Y=C。
      2. 应用德摩根定律得 X′⋅Y′X' \cdot Y'，即 (A′B)′⋅C′(A'B)' \cdot C'。
      3. 对 (A′B)′(A'B)' 再次应用德摩根定律，得 (A′′+B′)(A''+B')，即 (A+B′)(A+B')。
      4. 最终结果为 (A+B′)C′(A+B')C'。

2.2 布尔函数 (Boolean Functions)​

布尔函数由布尔变量、运算符和括号组成。它可以有多种表现形式，但其逻辑功能是唯一的。

  • 文字 (Literal): 一个变量的原变量或反变量（如 AA 或 A′A'）。
  • 乘积项 (Product term): 由“与”运算连接的若干文字（如 A′BCA'BC）。
  • 和项 (Sum term): 由“或”运算连接的若干文字（如 A+B′+CA+B'+C）。

核心结论: 一个布尔函数有唯一的真值表 (Truth Table) 表达，但可以有多种代数表达式和逻辑门电路实现。

用例: 函数 F1F_1 和 F2F_2 F1=x′y′z+x′yz+xy′F_1 = x'y'z + x'yz + xy' F2=x′z+xy′F_2 = x'z + xy' 尽管它们的代数表达式不同，但它们的真值表是完全相同的。通过代数化简可以证明 F1=F2F_1 = F_2：

F1=x′y′z+x′yz+xy′=x′z(y′+y)+xy′(分配律)=x′z⋅1+xy′(互补律)=x′z+xy′=F2(恒等律)\begin{align*} F_1 &= x'y'z + x'yz + xy' \\ &= x'z(y' + y) + xy' \quad &\text{(分配律)} \\ &= x'z \cdot 1 + xy' \quad &\text{(互补律)} \\ &= x'z + xy' = F_2 \quad &\text{(恒等律)} \end{align*}

F2F_2 的表达式更简单，意味着实现它所需的逻辑门更少，成本更低。因此，函数化简是数字逻辑设计的核心目标之一。

2.2.1 函数的补函数 (Complement of a Function)​

求一个函数 FF 的补函数 F′F'，最系统的方法是反复应用德摩根定律。一个更快捷的技巧是：

  1. 求对偶式 (Dual): 将原始表达式中的 ⋅\cdot 和 ++ 互换。
  2. 反转每个文字 (Complement each literal): 将表达式中的每个原变量变为反变量，反之亦然。

用例: 求 F=x′yz+xy′F = x'yz + xy' 的补函数 F′F'。

  1. 原始函数: F=(x′⋅y⋅z)+(x⋅y′)F = (x' \cdot y \cdot z) + (x \cdot y')
  2. 步骤 1：求对偶式: 将 ⋅\cdot 换成 ++，将 ++ 换成 ⋅\cdot。 Dual(F)=(x′+y+z)⋅(x+y′)\text{Dual}(F) = (x' + y + z) \cdot (x + y') 注意: 此时得到的并不是 F′F'，这只是一个中间步骤。
  3. 步骤 2：反转每个文字: 将 x′x' 换成 xx， yy 换成 y′y'， zz 换成 z′z'， xx 换成 x′x'。 F′=(x+y′+z′)⋅(x′+y)F' = (x + y' + z') \cdot (x' + y) 这就是最终结果。

2.3 范式与标准式 (Canonical and Standard Forms)​

2.3.1 最小项与最大项 (Minterms and Maxterms)​

对于一个 nn 变量的函数，其真值表有 2n2^n 行。每一行都对应一个最小项和一个最大项。

  • 最小项 (Minterm, mim_i): 一个包含全部 nn 个变量的乘积项。如果变量在对应行中的值为 00，则取反形式；如果为 11，则取原形式。
  • 最大项 (Maxterm, MiM_i): 一个包含全部 nn 个变量的和项。如果变量在对应行中的值为 00，则取原形式；如果为 11，则取反形式。

重要关系: 同一行的最小项和最大项互为反函数，即 Mi=mi′\mathbf{M_i = m_i'}。

3 变量 (x, y, z) 的最小项与最大项表示

行号xyz最小项 (mim_i)最大项 (MiM_i)
0000x′y′z′x'y'z'x+y+zx+y+z
1001x′y′zx'y'zx+y+z′x+y+z'
2010x′yz′x'yz'x+y′+zx+y'+z
3011x′yzx'yzx+y′+z′x+y'+z'
4100xy′z′xy'z'x′+y+zx'+y+z
5101xy′zxy'zx′+y+z′x'+y+z'
6110xyz′xyz'x′+y′+zx'+y'+z
7111xyzxyzx′+y′+z′x'+y'+z'

2.3.2 范式 (Canonical Forms)​

范式是函数的唯一、标准化的表达形式。

  1. 最小项之和 (Sum-of-Minterms, SoM)

    • 定义: 将真值表中函数值为 11 的所有行对应的最小项相“或”。
    • 表示法: F=∑m(i1,i2,...)F = \sum m(i_1, i_2, ...)，其中 i1,i2,...i_1, i_2, ... 是函数值为 11 的行号。
    • 用例: 若某函数在行 1, 3, 6, 7 处值为 1，则其 SoM 形式为： F=m1+m3+m6+m7=x′y′z+x′yz+xyz′+xyz=∑(1,3,6,7)F = m_1 + m_3 + m_6 + m_7 = x'y'z + x'yz + xyz' + xyz = \sum(1, 3, 6, 7)

  2. 最大项之积 (Product-of-Maxterms, PoM)

    • 定义: 将真值表中函数值为 00 的所有行对应的最大项相“与”。
    • 表示法: F=∏M(j1,j2,...)F = \prod M(j_1, j_2, ...)，其中 j1,j2,...j_1, j_2, ... 是函数值为 00 的行号。
    • 用例: 若某函数在行 0, 2, 4, 5 处值为 0，则其 PoM 形式为： F=M0⋅M2⋅M4⋅M5=(x+y+z)(x+y′+z)(x′+y+z)(x′+y+z′)=∏(0,2,4,5)F = M_0 \cdot M_2 \cdot M_4 \cdot M_5 = (x+y+z)(x+y'+z)(x'+y+z)(x'+y+z') = \prod(0, 2, 4, 5)

范式间的转换 SoM 和 PoM 可以相互转换。如果已知一个，另一个就由原形式中未包含的行号决定。 若 F=∑(1,3,6,7)，则 F=∏(0,2,4,5)\text{若 } F = \sum(1, 3, 6, 7) \text{，则 } F = \prod(0, 2, 4, 5) 推导: F=∑(1,3,6,7)  ⟹  F′=∑(0,2,4,5)=m0+m2+m4+m5F = \sum(1,3,6,7) \implies F' = \sum(0,2,4,5) = m_0+m_2+m_4+m_5 F=(F′)′=(m0+m2+m4+m5)′F = (F')' = (m_0+m_2+m_4+m_5)' 根据德摩根定律，F=m0′⋅m2′⋅m4′⋅m5′F = m_0' \cdot m_2' \cdot m_4' \cdot m_5' 因为 Mi=mi′M_i=m_i'，所以 F=M0⋅M2⋅M4⋅M5=∏(0,2,4,5)F = M_0 \cdot M_2 \cdot M_4 \cdot M_5 = \prod(0,2,4,5)

2.3.3 函数到范式的转换​

将一个普通布尔表达式转换为范式，需要将每个项都补充完整，使其包含所有变量。

  • 转为 SoM (最小项之和): 对每个乘积项，乘以 (A+A′)=1(A+A')=1 形式的缺失变量项。
    • 用例: 将 F=A+B′CF = A+B'C 转换为 SoM (假设为 3 变量 A, B, C)。 F=A+B′C=A⋅(B+B′)⋅(C+C′)+(A+A′)⋅B′C(补全缺失变量)=(AB+AB′)(C+C′)+AB′C+A′B′C=ABC+ABC′+AB′C+AB′C′+AB′C+A′B′C=A′B′C+AB′C′+AB′C+ABC′+ABC(等幂律去重，并按顺序排列)=m1+m4+m5+m6+m7=∑(1,4,5,6,7)\begin{align*} F &= A + B'C \\ &= A \cdot (B+B') \cdot (C+C') + (A+A') \cdot B'C \quad &\text{(补全缺失变量)} \\ &= (AB+AB')(C+C') + AB'C + A'B'C \\ &= ABC+ABC'+AB'C+AB'C' + AB'C + A'B'C \\ &= A'B'C + AB'C' + AB'C + ABC' + ABC \quad &\text{(等幂律去重，并按顺序排列)} \\ &= m_1 + m_4 + m_5 + m_6 + m_7 \\ &= \sum(1, 4, 5, 6, 7) \end{align*}
  • 转为 PoM (最大项之积): 先用分配律 X+YZ=(X+Y)(X+Z)X+YZ=(X+Y)(X+Z) 将函数转为“和之积”形式，再对每个和项，加上 AA′=0AA'=0 形式的缺失变量项。
    • 用例: 将 F=xy+x′zF = xy+x'z 转换为 PoM。 F=xy+x′z=(xy+x′)(xy+z)(应用分配律 A+BC=(A+B)(A+C) )=(x′+x)(x′+y)(z+x)(z+y)(再次应用分配律)=1⋅(x′+y)(x+z)(y+z)=(x′+y)(x+z)(共识律，或直接展开证明)=(x′+y+zz′)(x+z+yy′)(补全缺失变量)=(x′+y+z)(x′+y+z′)(x+y+z)(x+y′+z)=M4⋅M5⋅M0⋅M2=∏(0,2,4,5)\begin{align*} F &= xy+x'z \\ &= (xy+x')(xy+z) \quad &\text{(应用分配律 } A+BC=(A+B)(A+C) \text{ )}\\ &= (x'+x)(x'+y)(z+x)(z+y) \quad &\text{(再次应用分配律)}\\ &= 1 \cdot (x'+y)(x+z)(y+z) \\ &= (x'+y)(x+z) \quad &\text{(共识律，或直接展开证明)}\\ &= (x'+y+zz')(x+z+yy') \quad &\text{(补全缺失变量)}\\ &= (x'+y+z)(x'+y+z')(x+y+z)(x+y'+z) \\ &= M_4 \cdot M_5 \cdot M_0 \cdot M_2 \\ &= \prod(0, 2, 4, 5) \end{align*}

2.3.4 标准式与范式对比​

标准式 (Standard Form) 是比范式更普遍的表达，其项中不要求包含所有变量。

  • 与或式 (Sum-of-Products, SoP): 如 F=y′+xy+x′yz′F = y' + xy + x'yz'
  • 或与式 (Product-of-Sums, PoS): 如 F=x(y′+z)(x′+y+z′)F = x(y'+z)(x'+y+z')
特性范式 (Canonical Form)标准式 (Standard Form)
唯一性是。一个函数只有一种 SoM 和一种 PoM。否。一个函数可以有多种 SoP 和 PoS 形式。
变量要求每个项（最小项/最大项）必须包含所有输入变量。项中可以不包含所有输入变量。
表达式长度通常较长，文字和项较多。通常更短，是化简后的结果。
与真值表关系直接对应，可从真值表直接读出。不直接对应，是化简后的结果。
用途提供唯一的、标准化的函数描述。提供更简洁、电路实现成本更低的方案。

2.4 其他逻辑运算与逻辑门​

除了基本的 AND, OR, NOT，还有其他常用的逻辑运算和门电路。

运算名称表达式描述
NAND与非(xy)′(xy)'AND 后取反
NOR或非(x+y)′(x+y)'OR 后取反
XOR异或x⊕y=x′y+xy′x \oplus y = x'y+xy'输入相异时输出 1
XNOR同或(x⊕y)′=x′y′+xy(x \oplus y)' = x'y'+xy输入相同时输出 1
Buffer缓冲器xx信号增强，不改变逻辑

2.4.1 多输入逻辑门 (Multiple-Input Gates)​

  • AND, OR, XOR, XNOR: 具有交换律和结合律，可以直接扩展到多输入。

    • A+B+C=(A+B)+C=A+(B+C)A+B+C = (A+B)+C = A+(B+C)
    • A⊕B⊕C=(A⊕B)⊕C=A⊕(B⊕C)A \oplus B \oplus C = (A \oplus B) \oplus C = A \oplus (B \oplus C)
    • 多输入异或门 (XOR): 当输入中有奇数个 1 时，输出为 1。

  • NAND, NOR: 具有交换律，但不具有结合律。

    • (A⋅B)′⋅C)′≠(A⋅(B⋅C)′)′(A \cdot B)' \cdot C)' \neq (A \cdot (B \cdot C)')'
    • 因此，多输入 NAND 门被定义为所有输入先“与”再“非”，即 (ABC...)′(ABC...)'。
    • 多输入 NOR 门被定义为所有输入先“或”再“非”，即 (A+B+C...)′(A+B+C...)'。